package com.fulu.javabase.upperbench;

import org.junit.Test;

import java.math.BigDecimal;

/**
 * 面试题，有n个台阶，每一步能上1、2个台阶，问一共有几种上法
 *
 */
public class upperBenchTest {

    @Test
    public void test(){
        long start = System.currentTimeMillis();
        System.out.println(f(40));
        long end = System.currentTimeMillis();
        System.out.println(end - start);

        long start1 = System.currentTimeMillis();
        System.out.println(loop(40));
        long end1 = System.currentTimeMillis();
        System.out.println(end1 - start1);

        long start2 = System.currentTimeMillis();
        System.out.println(f2(40));
        long end2 = System.currentTimeMillis();
        System.out.println(end2 - start2);
    }

    /**
     * 递归
     * 提供n个台阶上法计算
     * 1个台阶1种
     * 2个台阶2种
     * @param n
     * @return
     */
    public int f(int n){
        if(n == 1 || n == 2){
            return n;
        }
        return f(n - 2) + f(n-1);
    }

    /**
     * 动态规划
     * @param n
     * @return
     */
    public int loop(int n){
        if(n == 1 || n == 2){
            return n;
        }

        // 一共有三个台阶的情况
        int back2 = 1;   // 去掉2个台阶，就是1个台阶，有1种走法
        int back1 = 2;   // 去掉一个台阶，就是2个台阶，有2种走法
        int sum = 0;   // 一共有多少走法

        for(int i = 3 ; i <= n; i++) {
            sum = back2 + back1;  // 三个台阶就是退一步和退两步的走法之和
            back2 = back1;   // 为4个台阶做准备，四个台阶退两步就是2个台阶，2种走法，所以刚好等于三个台阶退一步的走法数
            back1 = sum;   // 那么4个台阶退一步就是3个台阶，刚好等于上面算出的3个台阶的总走法
        }

        return sum;
    }


    /**
     * 另外一种动态规划写法，可以迈过 1 2 3 个台阶
     * @param n
     * @return
     */
    public String f2(int n){
        if(n < 1) return "0";
        if(n == 1) return "1";
        if(n == 2) return "2";
        if(n == 3) return "4";
        /* 如果是四个台阶，上法有7种，1-1-1-1，2-1-1，1-2-1，1-1-2，2-2，3-1，1-3
         * 可知 方法是前三种情况方法的总和 7=1+2+4
         * 通过这个规律进行计算
         */
        String [] step = new String[n];
        step[0] = "1";
        step[1] = "2";
        step[2] = "4";
        if(n<=3){
            return step[n-1];
        }
        for(int i=3;i<n;i++){
            step[i] = new BigDecimal(step[i-3]).add(new BigDecimal(step[i-2]).add(new BigDecimal(step[i-1]))).toString();
        }
        return step[n-1];
    }
}
